package com.mdnote.structure.recuirsion;


/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/25
 * @description 八皇后问题
 */
public class Queen8 {

    private int[] checkerboard;

    private int size;

    public Queen8(int size) {
        this.size = size;
        this.checkerboard = new int[size];
    }

    private static int counter = 0;

    /**
     * 展示期盼
     */
    public void show() {
        for (int i = 0; i < size; i++) {
            System.out.print(checkerboard[i] + " ");
        }
        System.out.println();
    }

    /**
     * 检查皇后是否合法
     * @param queen 皇后
     * @return  是否合法
     */
    public boolean judge(int queen) {

        for (int i = 0; i < queen; i++) {
            // 是否在同一列或者同一条斜线
            // 一旦发现前面有一个不行就不能执行了
            if (this.checkerboard[i] == this.checkerboard[queen] || Math.abs(i - queen) == Math.abs(this.checkerboard[i] - this.checkerboard[queen])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 寻找答案
     * @param queen 初始化皇后位置
     */
    public void check(int queen) {
        // Terminate
        if (queen == size) {
            // 展示答案
            show();
            // 计数
            counter++;
            return;
        }
        for (int i = 0; i < size; i++) {
            // current login 假定当前的位置合法
            this.checkerboard[queen] = i;
            // drill down 判断是否合法
            if (judge(queen)) {
                check(queen + 1);
            }
        }
    }

    public static void main(String[] args) {
        Queen8 queen8 = new Queen8(8);
        queen8.check(0);
        System.out.println("一共有" + counter + "钟可能");
    }
}
